--[[
十字链表aoi

TODO: 
1. 优化：改为跳表
2. 优化：按区域划分为多个十字链表
3. 每个obj自定义视野范围
--]]


local M = {
    aoi_head_x = {},  -- x轴头节点
    aoi_head_y = {},  -- y轴头节点
    aoi_radius = 10,   -- 视野范围（半径）
}

function M.new_aoi_obj(player_id, x, y)
    local aoi_obj = {}
    aoi_obj.player_id = player_id
    aoi_obj.x = x
    aoi_obj.y = y
    aoi_obj.prev_x = nil
    aoi_obj.prev_y = nil
    aoi_obj.next_x = nil
    aoi_obj.next_y = nil

    return aoi_obj
end

function M.init()
    M.aoi_head_x = M.new_aoi_obj(-1, 0, 0)
    M.aoi_head_y = M.new_aoi_obj(-1, 0, 0)
end

function M.create_aoi_obj(player_id, x, y)
    local aoi_obj = M.new_aoi_obj(player_id, x, y)

    M.insert_aoi_obj(aoi_obj)
    return aoi_obj
end

function M.test_print_list()
    local t = M.aoi_head_x
    while t.next_x do
        print("show aoi_list_x:", t.next_x.player_id, t.next_x.x)
        t = t.next_x
    end

    t = M.aoi_head_y
    while t.next_y do
        print("show aoi_list_y:", t.next_y.player_id, t.next_y.y)
        t = t.next_y
    end
end

function M.insert_aoi_obj(aoi_obj)
    local current = M.aoi_head_x
    if current.next_x and current.next_x.x < aoi_obj.x then
        current = current.next_x
    end

    aoi_obj.prev_x = current
    aoi_obj.next_x = current.next_x
    if current.next_x then
        current.next_x.prev_x = aoi_obj
    end
    current.next_x = aoi_obj

    current = M.aoi_head_y
    if current.next_y and current.next_y.y < aoi_obj.y then
        current = current.next_y
    end

    aoi_obj.prev_y = current
    aoi_obj.next_y = current.next_y
    if current.next_y then
        current.next_y.prev_y = aoi_obj
    end
    current.next_y = aoi_obj

    print("insert_aoi_obj", aoi_obj.player_id)
    M.test_print_list()
end

function M.remove_aoi_obj(aoi_obj)
    if not aoi_obj then
        return
    end

    aoi_obj.prev_x.next_x = aoi_obj.next_x
    if aoi_obj.next_x then
        aoi_obj.next_x.prev_x = aoi_obj.prev_x
    end

    aoi_obj.prev_y.next_y = aoi_obj.next_y
    if aoi_obj.next_y then
        aoi_obj.next_y.prev_y = aoi_obj.prev_y
    end

    print("remove_aoi_obj", aoi_obj.player_id)
    M.test_print_list()
end

function M.update_aoi_obj(aoi_obj, new_x, new_y)
    M.remove_aoi_obj(aoi_obj)
    aoi_obj.x = new_x
    aoi_obj.y = new_y
    M.insert_aoi_obj(aoi_obj)
end

function M.query_range(center_x, center_y)
    local result = {}
    local min_x = center_x - M.aoi_radius
    local max_x = center_x + M.aoi_radius
    local min_y = center_y - M.aoi_radius
    local max_y = center_y + M.aoi_radius

    -- 找到x链表的起始节点
    local current = M.aoi_head_x.next_x
    if current and current.x < min_x then
        current = current.next_x
    end

    -- 在x范围内，再比较y
    while current and current.x <= max_x do
        if current.y >= min_y and current.y <= max_y then
            table.insert(result, current)
        end

        current = current.next_x
    end

    return result
end


M.init()
return M